/*************************************************************************
	> File Name: leetcode23.合并K个升序链表_v3.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 五  9/24 17:28:19 2021
 ************************************************************************/

//使用优先队列合并
//时间复杂度：O(kn x logk)
//空间复杂度: O(k)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        //注意：此处函数内部使用>符号的意思是，如果val>rhs.val，就要交换二者的位置，否则就是正常的位置
        //重载运算符可以理解为return的条件如果为真，就需要交换位置，然后看到底是大的值还是小的值在前面，来判断是大根堆还是小根堆
        bool operator<(const Status &rhs) const { //rhs（right hand side)，一般用于运算符，表示右操作符
            return val > rhs.val; //小根堆
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<Status> q;
        for (auto node : lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *pre = &head;
        while (!q.empty()) {
            auto node = q.top();
            q.pop();
            pre->next = node.ptr;
            pre = pre->next;
            if (node.ptr->next) q.push({node.ptr->next->val, node.ptr->next});
        }
        return head.next;
    }
};
